package FourthWeek;

public class Monday {
    //33、搜索旋转排序数组
    public int search(int[] nums, int target) {
        //我们可以使用二分查找，因为是从有序数组旋转n次形成的nums，我们定义任意一个mid会把其分成一段有序一段无序
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int left = 0,right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }else if (nums[0] <= nums[mid]) {
                //有序的一段，在有序的一段区间里面去寻找
                if (target < nums[mid] && nums[0] <= target) {
                    //nums[0] <= target是为了保证 target这个数据是在有序的这一段中，如果不存在就去无序中寻找
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }else {
                if (target > nums[mid] && nums[n - 1] >= target) {
                    //nums[n - 1] >= target是为了保证 target这个数据是在无序的这一段中，如果不存在就去有序中寻找
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}
